//从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任
//意数字。A 不能视为 14。 
//
// 
//
// 示例 1: 
//
// 输入: [1,2,3,4,5]
//输出: True 
//
// 
//
// 示例 2: 
//
// 输入: [0,0,1,2,5]
//输出: True 
//
// 
//
// 限制： 
//
// 数组长度为 5 
//
// 数组的数取值为 [0, 13] . 
// Related Topics 数组 排序 👍 157 👎 0


package leetcode.editor.cn1;

//Java：

/**
 * 从扑克牌中随机抽5张牌，判断是不是一个顺子，
 * 即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 * 输入: [1,2,3,4,5]
 * 输出: True
 * <p>
 * 输入: [0,0,1,2,5]
 * 输出: True
 */
public class BuKePaiZhongDeShunZiLcof {
    public static void main(String[] args) {
        Solution solution = new BuKePaiZhongDeShunZiLcof().new Solution();
        // TO TEST
        System.out.println(solution.isStraight(new int[]{7, 8, 0, 9, 10, 11}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isStraight(int[] nums) {
            // 冒泡排序
            if (nums.length < 5)
                return false;
            int nlen = nums.length, tmp = -1;
            // 冒泡排序效率低下
            // 冒泡排序
            quickSort(0, nlen - 1, nums);

            int sum = 0;
            for (int i = 0; i < nlen; i++) {
                if (nums[i] == 0)
                    sum = sum + 1;
            }

            int totalZero = 0;
            for (int i = sum; i < nlen - 1; i++) {
                if (nums[i] == nums[i + 1]
                        || (nums[i] < 0 || nums[i] > 13)
                        || (nums[i + 1] < 0 || nums[i + 1] > 13))
                    return false;
                if (nums[i] + 1 != nums[i + 1]) {
                    totalZero = totalZero + nums[i + 1] - nums[i] - 1;
                }
            }
            if (totalZero > sum)
                return false;
            return true;
        }

        /**
         * 冒泡排序
         *
         * @param nums
         */
        public void bubbling(int[] nums) {
            int nlen = nums.length, tmp = -1;
            for (int i = 1; i <= nlen; i++) {
                for (int j = 0; j < nlen - i; j++) {
                    if (nums[j] > nums[j + 1]) {
                        tmp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = tmp;
                    }
                }
            }
        }

        /**
         * 分治排序
         *
         * @param i
         * @param j
         * @param nums
         */
        public void quickSort(int i, int j, int[] nums) {
            if (i > j)
                return;
            int partitionIndex = partition(i, j, nums);
            quickSort(i, partitionIndex - 1, nums);
            quickSort(partitionIndex + 1, j, nums);
        }

        public int partition(int i, int j, int[] nums) {
            int l = i, r = j, base = nums[i];
            while (i < j) {
                while (i < j && nums[j] > base)
                    j--;
                while (i < j && nums[i] <= base)
                    i++;
                if (i < j) {
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
            nums[l] = nums[i];
            nums[i] = base;
            return i;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
